
/**
 * 数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
 * 给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
 */

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 暴力查找，内存，时间超出限制
// var smallestDistancePair = function (nums, k) {
//   let n = nums.length
//   const res = []
//   for (let i = 0; i < n - 1; i++) {
//     for (let j = i + 1; j < n; j++) {
//       res.push(Math.abs(nums[i] - nums[j]))
//     }
//   }
//   return res.sort((a, b) => {
//     return a - b
//   })[k - 1]
// };

// console.log(smallestDistancePair([1, 1, 1], 2));
// smallestDistancePair([1, 5, 8, 2], 3)

// 优化，使用二分查找

var smallestDistancePair = function (nums, k) {
  debugger
  nums.sort()
  // 最大差距 =  nums[n - 1] - nums[0]
  let n = nums.length, left = 0, right = nums[n - 1] - nums[0]
  while (left <= right) {
    const mid = Math.floor((right + left) / 2)
    let cnt = 0
    for (let j = 0; j < n; j++) {
      const i = binarySearch(nums, j, nums[j] - mid)
      cnt += j - i
    }
    if (cnt >= k) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return left
}

// 
const binarySearch = function (nums, end, target) {
  debugger
  let left = 0, right = end;
  while (left < right) {
    const mid = Math.floor((left + right) / 2)
    if (nums[mid] < target) {
      left = mid + 1
    } else {
      right = mid
    }
  }
  return left
}

console.log(smallestDistancePair([1, 5, 8, 2], 3));

// 二分 + 双指针
var smallestDistancePair = function (nums, k) {
  nums.sort((a, b) => a - b);
  let n = nums.length, left = 0, right = nums[n - 1] - nums[0];
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    let cnt = 0;
    for (let i = 0, j = 0; j < n; j++) {
      while (nums[j] - nums[i] > mid) {
        i++;
      }
      cnt += j - i;
    }
    if (cnt >= k) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}